干货！英诺森自然语言核心技术之分词——Trie字典树

↑ 点击上方蓝色文字，FOLLOW US

文：易爽

NLP（Natural Language Processing）自然语言处理，无疑是目前最火的AI研究方向之一，历经了复杂的规则系统到现在的各种深度学习模型的技术转变，已经是一个成熟的技术体系。虽然距离真正的AI还有一定距离，但是纵观目前NLP已经可以完成的任务，比如自然语言翻译、阅读理解、文本分类、语音翻译、智能对话等等，其完成的效果已经开始慢慢逼近人类完成同样任务的水平，18年Google在I/O开发者大会上推出了Duplex人工智能语音助手，已经在部分任务上通过了图灵测试。

这次希望通过一套系列文章，帮助大家理解NLP的核心技术同时能够掌握部分的实现细节，提高公司整体在AI方向上的战略思考和技术发展方向的预判。系列的内容目前大致安排如下，敬请期待：

• Trie字典树
• 新词发现，从HMM到CRF的原理与源码分析
• Word2Vec的应用与实践
• RNN家族
• transformer家族
• NLP前沿

我们知道词是最基本的文本单元，具备最基本的语义，中文当中的基本单元可以精确到字，词的界定相对困难；在英文中一般词与词之间用空格符号分隔，分词相对简单。分词作为NLP的第一个步骤是十分重要的，会影响到计算机对于文本的理解。中文分词一般有三个问题：

• 分词规则（本文主要研究问题），其效率和准确度都是很重要的；
• 消除歧义，有点类似古文的「句读」，分词不同会有完全不同的含义，比如：”结婚/的/和尚/未结婚/的“，“结婚/的/和/尚未/结婚/的”；
• 未登录词的识别（有些词汇我们没有录入词典，但希望算法识别出来）；

Trie字典树

接触过计算机算法的人明白一个线性表的顺序查找时间复杂度为O(n)，二分搜索树的查询时间复杂度为O(log⁡n)，他们的效率都与数据当中元素的个数相关，元素越多查询时间越长。在词典分词的任务中，我们一般会维护一个词典，里面存储了所有可能的词汇，在分词的时候，会遍历待分词的文本和词典，当查询到文本中一个词在词典中，则将此词分隔出来。由于NLP分词任务会有很多的文本需要分词，并且词典可能也是上百万级别的大小，那么查询的效率是关键因素。Trie词典树(主要用于存储字符串)查找速度主要和它的元素(字符串)的长度相关O(w)，这相对线性表和二分搜索树是很大的性能提升。Trie字典树主要用于存储和查询字符串，Trie 的每个 Node 保存一个字符。用链表来描述的话，就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。例如我们往字典树中插入see、sea、pain、paint四个单词，Trie字典树如下所示，Trie的结构具备一定的高效遍历能力的，如果只考虑小写的26个字母，那么Trie字典树的每个节点都可能有26个子节点。

Trie字典树的构建

本文使用Node这一数据结构来实现一个高效的Trie字典树，字典树将字符串的每个字符作为一个Node节点，Node主要有以下组成：节点的子节点；节点保存的值；节点是否是一个词汇；以下是Node节点的数据结构：

class Node():
    def __init__(self):
        self.next = {}
        self.val = None
        self.isword = False

以下是Trie树的数据结构：

class Trie(object):
    def __init__(self):
        self.root = Node()
        self.size = 0

Trie需要实现以下的方法和接口：

    def add(self, key, val):
        """
        :param key:需要加入的词汇
        :param val:词汇本身或者对应的词性
        :return:词汇是否添加成功
        """
        raise NotImplementedError

    def __contians__(self, word):
        raise NotImplementedError

    def exist(self, word):
        """
        :param word:
        :return: 当前词汇判断是否存在于Trie前缀树
        """
        raise NotImplementedError

    def find(self, sent, start=0):
        """
        :param sent: 待查找的句子
        :param start: 从句子的哪个位置开始查找
        :return: 元组，包含：查找到的字符串、字符串的值（词性）、
                当前查找的起始索引、字符串结束位置索引
        """
        raise NotImplementedError

    def get(self, sent):
        """
        :param sent: 文本字符串
        :return: 元组包含三个列表：词汇列表、词性列表、索引列表
        """
        raise NotImplementedError

    def delete(self, word):
        """
        :param word: 需要删除的词汇
        :return:
        """
        raise NotImplementedError

---

我们重点挑选几个函数方法实现来讲解：首先是Trie构建的关键函数add：代码解释：类似于键值对的构建方式，需要添加新的节点直接取节点的next属性

    def add(self, key, val):
        """
        :param key:需要加入的词汇
        :param val:词汇本身或者对应的词性
        :return:
        """
        # build the tree
        curr = self.root
        for k in key:
            if not k in curr.next:
                curr.next[k] = Node()
            curr = curr.next[k]
        if not curr.isword:
            self.size += 1
            curr.val = val
            curr.isword = True

---

__contains__方法判断词汇是否存在于字典树当中，exist只是调用了__contains__：代码解释：从root节点开始遍历字典树，判断当前的字符串的某一个字符是否存在

def __contains__(self, word):
    curr = self.root
    for p in range(len(word)):
        if word[p] in curr.next:
            curr = curr.next[word[p]]
        else:
            return False
    if curr.isword:
        return True
    return False

---

delete方法相对繁琐，但是增加了字典树的动态修改能力 代码解释：Trie的删除操作就稍微复杂一些，主要分为以下3种情况：

1. 如果单词是另一个单词的前缀：如果待删除的单词是另一个单词的前缀，只需要把该单词的最后一个节点的 isword 的改成false比如Trie中存在 panda 和 pan 这两个单词，删除 pan ，只需要把字符 n 对应的节点的 isword改成 false 即可：

2. 如果单词的所有字母的都没有多个分支，删除整个单词，如果单词的所有字母的都没有多个分支（也就是说该单词所有的字符对应的Node都只有一个子节点），则删除整个单词，例如要删除如下图的see单词，如下图所示：

3. 如果单词的除了最后一个字母，其他的字母有多个分支

def delete(self, word):
    """
    :param word: 需要删除的词汇
    """
    curr = self.root
    branch_idx = -1
    branch_node = None

    for p in range(len(word)):
        # 不存在字符串
        if word[p] not in curr.next:
            return False
        # 当前节点子节点还有分支
        child = curr.next[word[p]]
        if len(child.next) > 1:
            branch_idx = p
            branch_node = child
        curr = child

    # word后面还有分支
    if len(curr.next) > 0:
        if curr.isword:
            curr.isword = False
            self.size -= 1
            return True
        # 单词只是前缀
        return False

    # 单词的所有字母没有分支
    if branch_idx == -1:
        del self.root.next[word[0]]
        self.size -= 1
        return True
    # 单词的中间部分有分支，删除这个节点后面的节点
    if branch_idx != len(word) - 1:
        del branch_node.next[word[branch_idx + 1]]
        self.size -= 1
        return True
    return False

---

序列化方法serialize是为了方便字典树的保存和加载 代码解释：用Node和next结构形成的字典树无法序列化，只有通过先序遍历的方式将Trie转变成嵌套的dict；嵌套dict无法满足之前的delete这样复杂的操作，却可以满足查找、分词、加载、保存等基本功能；得到序列化字符串之后只需要eval(data)就可以编译成嵌套的dict，接下来就方便通过反序列化deserialize的方式加载并构建成Trie字典树；

def serialize(self, data, k, cur, d=0):
    """
    序列化，将构建好的trie树转变成嵌套词典字符串，preorder of tree
    :param data:初始字符串
    :param k:每次递归传递的键
    :param cur:当前递归的节点
    :param d:递归深度
    """
    if d == 0:
        data += '{'
    if k:
        data += '"' + k + '"' + ':' + '{'
        if cur.next:
            if cur.isword:
                data += "'val'" + ':' + '"' + cur.val + '"' + ','
        else:
            if cur.isword:
                data += "'val'" + ':' + '"' + cur.val + '"' + '}'

     for i, c in enumerate(cur.next):
        data = self.serialize(data, c, cur.next[c], d + 1)
        if i < len(cur.next) - 1:
            data += ','
        else:
            data += '}'
    return data

---

最后针对Trie字典树的测试使用也十分方便：

    t = Trie()
    # 加载部分字典
    t.add('5G', 'IND')
    t.add('5GT', 'GAME')
    t.add('GS', 'GS')
    t.add('5GS', '5GS')
    t.add('she', 'she')
    t.add('hers', 'hers')
    t.add('17**01', 'BOND')
    t.add('****', 'COMP')
    string = t.serialize('', '', t.root) # 序列化保存
    data = eval(string) # 解码序列化字符串
    print(data)
    t.root = Node()
    t.deserialize(data, t.root, '') # 反序列化字符串重构为新的trie树
    string = t.serialize('', '', t.root)
    data = eval(string)
    print(data)
    print('5G' in t)  # True
    t.delete('5GS')  # True
    print('5GS' in t)  # False
    print(t.get('“17**01”债实质性违约，****信用等级,hello world 5G and GS'))

---

分词工具的实现

分词工具一般可以根据Trie字典树的构建来完善，因为我们已经有了多词查询，现在只需要增加一些策略完善最终的分词。

代码解释：

1. 这个分词类Qseg实现了Trie字典树的加载和保存，加载了70w的文本词库，最后以json文件格式保存；
2. 笔者在普通分词基础上增加了英文和数字组合词汇的分词，参考ensplit方法；
3. 最终通过seg方法实现了完整的分词结果拼接；
4. 部分代码折叠，切分具体实现省略，基本上是循环和拼接过程；

分词使用方式：

if __name__ == '__main__':
    # xmnlp.set_userdict('../data/words.txt')
    import time
    t = Trie()  # initialize the trie
    # ------
    qs = Qseg()
    s1 = time.time()
    qs.seg(t, '这是什么4G手机厂商')
    e1 = time.time()
    print('loading dicts and building ac use {:.2f} seconds'.format(e1 - s1))
    s2 = time.time()
    sent = """赵军说这次疫情结果很严重，影响了5G业务的扩展"""
    print(qs.seg(t, sent))
    e2 = time.time()
    print('seg new sent use {:.2f} m-seconds'.format((e2 - s2) * 1000))

分词结果，加载词库数量在70w词左右，用时11.8秒，一条文本分词用时0.16毫秒，速度很快：loading dicts and building ac use 11.89 seconds ['赵军', '说', '这次', '疫情', '结果', '很', '严重', '，', '影响', '了', '5G', '业务', '的', '扩展'] seg new sent use 0.16 m-seconds

分词策略

• 正向最大匹配法（FMM） 针对以上代码的seg方法，默认是采用此策略来进行匹配，
  FMM的步骤是：（1）从左向右取待分汉语句的m个字作为匹配字段，m为词典中最长词的长度。（2）查找词典进行匹配。（3）若匹配成功，则将该字段作为一个词切分出去。（4）若匹配不成功，则将该字段最后一个字去掉，剩下的字作为新匹配字段，进行再次匹配。（5）重复上述过程，直到切分所有词为止。

• 逆向最大匹配法（RMM）
  RMM的基本原理与FMM基本相同，不同的是分词的方向与FMM相反。RMM是从待分词句子的末端开始，也就是从右向左开始匹配扫描，每次取末端m个字作为匹配字段，匹配失败，则去掉匹配字段前面的一个字，继续匹配。

• 双向最大匹配法（Bi-MM） Bi-MM是将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较，然后按照最大匹配原则，选取词数切分最少的作为结果。据SunM.S.和Benjamin K.T.（1995）的研究表明，中文中90.0%左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0%的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0%的句子，使用正向最大匹配法和逆向最大匹配法的切分虽然重合但是错的，或者两种方法切分不同但结果都不对（歧义检测失败）。双向最大匹配的规则是：（1）如果正反向分词结果词数不同，则取分词数量少的那个。（2）如果分词结果词数相同：1）分词结果相同，没有歧义，返回任意一个。2）分词结果不同，返回其中单字数量较少的那个。比如：上述例子中词数相同，但结果不同，逆向最大匹配法的分词结果单字个数是1，所以返回的是逆向最大匹配法的结果。参见以下代码示例：

def bicut(self, sent): res_fmm = self.fmm.seg(sent) res_rmm = self.rmm.seg(sent) if len(res_fmm) == len(res_rmm): if res_fmm == res_rmm: return res_fmm else: f_word_count = len([w for w in res_fmm if len(w)==1]) r_word_count = len([w for w in res_rmm if len(w)==1]) return res_fmm if f_word_count < r_word_count else res_rmm else: return res_fmm if len(res_fmm) < len(res_rmm) else res_rmm

总结

通过原理解释和部分示例代码的讲解，我们完成了NLP的第一个步骤即分词的功能实现，这个工具笔者参考了jieba、HanLP^[1]、xmnlp等开源项目，并结合自身实际工作的需求做了一定的二次开发，如果想进一步研究分词，可以参考Aho Corasick^[2]算法以及Aho Corasick算法的实现Double Array Aho Corasick^[3]算法，限于篇幅本文不做赘述。本文实现了一个性能较高的词典分词工具，经过以前工作不同场景的检验具备较好的性能和稳定性。在下一篇我会着重介绍HMM（隐马尔科夫）模型和CRF（条件随机场）模型，从而解决出现未录入词的情况下，算法如何发现新词。

参考资料

[1]

HanLP: http://www.hanlp.com/

[2]

AC: https://www.hankcs.com/program/algorithm/implementation-and-analysis-of-aho-corasick-algorithm-in-java.html

[3]

Double Array AC: https://www.hankcs.com/program/algorithm/aho-corasick-double-array-trie.html

英诺森是一家创新驱动、深耕行业、全球发展，为企业客户提供数字化解决方案的公司。公司专注于技术融合与价值创造，帮助客户改进管理流程，驱动业务增长，实现数字化转型。公司拥有全球化的服务网络，在南京、北京、上海、深圳、西安、香港、蒙特利尔、爱丁堡、波士顿等地设立公司及分支机构，在海内外设有多个研发中心。

● 微信号 : Inossem ●

长按识别二维码关注我们